\chapter{集合}\label{ch16}

\emph{We all behave like Maxwell’s demon. Organisms organize. In everyday experience lies the reason sober physicists across two centuries kept this cartoon fantasy alive. We sort the mail, build sand castles, solve jigsaw puzzles, separate wheat from chaff, rearrange chess pieces, collect stamps, alphabetize books, create symmetry, compose sonnets and sonatas, and put our rooms in order, and all this we do requires no great energy, as long as we can apply intelligence.}

\begin{flushright}
    ——James Gleick, The Information: A History, a Theory, a Flood
\end{flushright}

Rust标准库里包含几种\emph{集合(collection)}，它们是在内存中存储数据的泛型类型。我们已经在本书的很多地方使用过集合，例如\texttt{Vec}和\texttt{HashMap}。在本章中，我们将详细介绍这两种类型的方法，以及其他六种标准集合。但在我们开始之前，让我们先讨论一下Rust的集合和其他语言中的集合的一些不同之处。

首先，移动和借用无处不在。Rust使用移动来避免深拷贝。这就是为什么\\
\texttt{Vec<T>::push(item)}方法以值获取参数，而不是以引用。值会被移动进vector。\hyperref[ch04]{第4章}中的图展示了实践中的表现：在Rust中把一个\texttt{String}添加到\texttt{Vec<String>}中很快，因为Rust不需要拷贝字符串的字符数据，字符串的所有权归属也总是很清楚。

其次，当集合改变大小或者被修改的同时还有指向它们的数据的指针时，Rust不会有无效性错误——即悬垂指针。无效性错误是C++中另一种未定义行为的来源，即使在内存安全的语言中也可能导致\texttt{ConcurrentModificationException}。Rust借用检查器会在编译器检查出它们。

最后，Rust没有\texttt{null}，因此我们将在其他语言中需要\texttt{null}的地方看到\texttt{Option}。

除了这些不同之外，Rust的集合可能和你预期的差不多。如果你是经验丰富的程序员并且时间不多，你可以跳过这部分，但不要跳过\nameref{entry}。

\section{概述}

\hyperref[t16-1]{表16-1}展示了Rust的8种标准集合。它们都是泛型类型。

\begin{table}[htb]
    \centering
    \caption{标准集合总结}
    \label{t16-1}
    \begin{tabular}{p{0.2\textwidth}p{0.2\textwidth}lll}
        \hline
        \multirow{2}{*}{\textbf{集合}}  & \multirow{2}{*}{\textbf{说明}} & \multicolumn{3}{l}{\textbf{其他语言中的类似集合类型}} \\
        \cline{3-5}
         & & \textbf{C++} & \textbf{Java} & \textbf{Python} \\
        \hline

        \texttt{Vec<T>} & 可增长的数组  & \texttt{vector} & \texttt{ArrayList} & \texttt{list}  \\
        \rowcolor{tablecolor}
        \texttt{VecDeque<T>} & 双端队列(可增长环形缓冲区) & \texttt{deque} & \texttt{ArrayDeque} & \texttt{collections.deque} \\
        \texttt{LinkedList<T>} & 双向链表 & \texttt{list} & \texttt{LinkedList} & —— \\
        \rowcolor{tablecolor}
        \texttt{BinaryHeap<T> where T: Ord} & 大顶堆 & \texttt{priority\_queue} & \texttt{PriorityQueue} & \texttt{heapq} \\
        \texttt{HashMap<K, V> where K: Eq + Hash} & 键值哈希表 & \texttt{unordered\_map} & \texttt{HashMap} & \texttt{dict} \\
        \rowcolor{tablecolor}
        \texttt{BTreeMap<K, V> where K: Ord} & 有序键值表 & \texttt{map} & \texttt{TreeMap} & —— \\
        \texttt{HashSet<T> where T: Eq + Hash} & 基于哈希的无序集合 & \texttt{unordered\_set} & \texttt{HashSet} & \texttt{set} \\
        \rowcolor{tablecolor}
        \texttt{BTreeSet<T> where T: Ord} & 有序集合 & \texttt{set} & \texttt{TreeSet} & —— \\
    \end{tabular}
\end{table}

\texttt{Vec<T>}、\texttt{HashMap<K, V>}、\texttt{HashSet<T>}是最常用的集合类型。其他的集合都有适用的场景。这一章将轮流讨论每一个集合类型：

\codeentry{Vec<T>}
\hangparagraph{一个可增长的、在堆上分配的、\texttt{T}类型值的数组。本章中大约一半的篇幅专门介绍\texttt{Vec}和它的常用方法。}

\codeentry{VecDeque<T>}
\hangparagraph{类似于\texttt{Vec<T>}，但是用作先进先出队列会更好。它支持高效地在首部和尾部添加或移除元素，但这种能力的代价是其他操作会稍微慢一点。}

\codeentry{BinaryHeap<T>}
\hangparagraph{一个优先队列。\texttt{BinaryHeap}中的值按照一定结构组织，因此总是可以高效地找到和移除最大值。}

\codeentry{HashMap<K, V>}
\hangparagraph{一个键值对的表。通过键查找值很快速。表中的条目以任意顺序存储。}

\codeentry{BTreeMap<K, V>}
\hangparagraph{类似于\texttt{HashMap<K, V>}，但按键的顺序保持条目有序。一个\texttt{BTreeMap<String, i32>}按照\texttt{String}的比较顺序存储条目。除非你需要条目保持有序，否则\texttt{HashMap}会更快。}

\codeentry{HashSet<T>}
\hangparagraph{类型\texttt{T}的值的集合。添加和删除元素都很快，查询一个值是否在集合中也很快。}

\codeentry{BTreeSet<T>}
\hangparagraph{类似于\texttt{HashSet<T>}，但保持元素有序。同样，除非你想要数据保持有序，否则\texttt{HashSet}会更快。}

因为\texttt{LinkedList}很少使用（并且在大多数情况下都有更好的替代，无论是性能还是接口），因此我们不会在这里介绍它。

\section{\texttt{Vec<T>}}

我们假设你对\texttt{Vec}已经有了一定了解，因为我们在本书的很多地方都已经使用过它。简要的介绍见\nameref{vector}。这里我们只会描述它的方法以及深入它的内部工作原理。

最简单的创建vector的方式是使用\texttt{vec!}宏：
\begin{minted}{Rust}
    // 创建一个空的vector
    let mut numbers: Vec<i32> = vec![];

    // 用给定的内容创建一个vector
    let words = vec!["step", "on", "no", "pets"];
    let mut buffer = vec![0u8; 1024];   // 1024个0字节
\end{minted}

正如我们在\hyperref[ch04]{第4章}所述，vector有三个字段：长度、容量、和一个指向堆上分配的缓冲区的指针。\hyperref[f16-1]{图16-1}展示了上面的vector在内存中的视图。空vector \texttt{numbers}的初始长度为0。在它添加第一个元素之前不会有堆内存被分配。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/f16-1.png}
    \caption{vector的内存布局：words的每个元素是一个由指针和长度组成的\texttt{\&str}值}
    \label{f16-1}
\end{figure}

类似于所有集合，\texttt{Vec}实现了\texttt{std::iter::FromIterator}，因此你可以对任何迭代器调用\texttt{.collect()}方法来创建一个vector，正如\nameref{BuildColl}中所述：
\begin{minted}{Rust}
    // 将一个其他集合转换成vector
    let my_vec = my_set.into_iter().collect::<Vec<String>>();
\end{minted}

\subsection{访问元素}
通过索引访问数组、切片或vector的元素非常直观：
\begin{minted}{Rust}
    // 获取一个元素的引用
    let first_line = &lines[0];

    // 获取一个元素的拷贝
    let fifth_number = numbers[4];          // 需要Copy
    let second_number = lines[1].clone();   // 需要Clone

    // 获取一个切片的引用
    let my_ref = &buffer[4..12];

    // 获取一个切片的拷贝
    let my_copy = buffer[4..12].to_vec();   // 需要Clone
\end{minted}

当索引越界时所有这些方式都会panic。

Rust对数字类型很挑剔，vector也不例外。vector的长度和索引都是\texttt{usize}类型。尝试使用\texttt{u32}、\texttt{u64}、\texttt{isize}作为vector的索引会导致错误。必要时你可以使用\texttt{n as usize}来转换，见\nameref{cast}。

有几种方法提供了便捷地访问vector或切片的特定元素的方法（注意所有的切片方法都能用于数组和vector）：

\codeentry{slice.first()}
\hangparagraph{返回\texttt{slice}的第一个元素的引用。返回类型是\texttt{Option<\&T>}，因此如果\texttt{slice}为空时返回值为\texttt{None}，不为空时返回值为\texttt{Some(\&slice[0])}：}
\begin{minted}{Rust}
    if let Some(item) = v.first() {
        println!("We got one! {}", item);
    }
\end{minted}

\codeentry{slice.last()}
\hangparagraph{和上边相似，不过返回最后一个元素的引用。}

\codeentry{slice.get(index)}
\hangparagraph{返回\texttt{slice[index]}的引用，如果存在的话。如果\texttt{slice}的元素数量小于\texttt{index+1}，那么返回\texttt{None}：}
\begin{minted}{Rust}
    let slice = [0, 1, 2, 3];
    assert_eq!(slice.get(2), Some(&2));
    assert_eq!(slice.get(4), None);
\end{minted}

\codeentry{slice.first\_mut(), slice.last\_mut(), slice.get\_mut(index)}
\hangparagraph{与上面的类似，不过借用\texttt{mut}引用：}
\begin{minted}{Rust}
    let mut slice = [0, 1, 2, 3];
    {
        let last = slice.last_mut().unwrap();   // 最后一个元素类型：&mut i32
        assert_eq!(*last, 3);
        *last = 100;
    }
\end{minted}

因为以值返回\texttt{T}意味着移动它，因此访问元素的方法通常返回元素的引用。

一个例外是\texttt{.to\_vec()}方法，它获取拷贝：

\codeentry{slice.to\_vec()}
\hangparagraph{克隆整个切片，返回一个新的vector：}
\begin{minted}{Rust}
    let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    assert_eq!(v.to_vec(),
               vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    assert_eq!(v[0..6].to_vec(),
               vec![1, 2, 3, 4, 5, 6]);
\end{minted}
\hangparagraph{只有当元素可以拷贝时这个方法才可用，即\texttt{where T: Clone}}。

\subsection{迭代}\label{Iteration}
vector和切片可以以值或者以引用迭代，遵循\nameref{IntoIter}中介绍的模式：
\begin{itemize}
    \item 迭代\texttt{Vec<T>}会产生\texttt{T}类型的item。元素被逐个移出vector消耗掉。
    \item 迭代\texttt{\&[T; N], \&[T], \&Vec<T>}——即数组、切片或vector的引用——会产生\texttt{\&T}类型的item，每一个item指向一个元素，不会移动元素。
    \item 迭代\texttt{\&mut [T; N], \&mut [T], \&mut Vec<T>}产生\texttt{\&mut T}类型的item。
\end{itemize}

数组、切片和vector还有\texttt{.iter()}和\texttt{.iter\_mut()}方法（见\nameref{IterMethod}）创建产生元素的引用的迭代器。

我们将在\nameref{split}中介绍一些更有趣的迭代切片的方法。

\subsection{增长和缩减vector}
数组、切片或vector的\emph{长度(length)}是它包含的元素的数量：

\codeentry{slice.len()}
\hangparagraph{返回一个\texttt{slice}的长度，类型为\texttt{usize}。}

\codeentry{slice.is\_empty()}
\hangparagraph{当\texttt{slice}不包含元素时为真（即\texttt{slice.len() == 0}）。}

本节剩余的方法都是关于增长和缩减vector。它们不能用于数组和切片，因为这两种类型一旦被创建之后就不能改变大小。

vector的所有元素都存储在一个在堆上分配的连续内存块中。vector的\emph{容量(capacity)}是指当前的内存块最多能存储的元素数量。\texttt{Vec}通常会替你管理容量，当需要增长时它会自动分配更大的缓冲区并把元素都移动过去。还有一些显式管理容量的方法：

\codeentry{Vec::with\_capacity(n)}
\hangparagraph{创建一个容量为\texttt{n}的新的空vector。}

\codeentry{vec.capacity()}
\hangparagraph{返回\texttt{vec}的容量，类型是\texttt{usize}。\texttt{vec.capacity() >= vec.len()}总是为真。}

\codeentry{vec.reserve(n)}
\hangparagraph{保证vector的剩余空间至少还能再存储\texttt{n}个或更多元素：即\texttt{vec.capacity()}至少是\texttt{vec.len() + n}。如果已经有足够的空间，它不做任何事。否则，它会分配一个更大的缓冲区并且把vector的内容移动过去。}

\codeentry{vec.reserve\_exact(n)}
\hangparagraph{类似于\texttt{vec.reserve(n)}，但告诉\texttt{vec}不要为未来的增长分配额外的空间。调用它之后，\texttt{vec.capacity()}等于\texttt{vec.len() + n}。}

\codeentry{vec.shrink\_to\_fit()}
\hangparagraph{当\texttt{vec.capacity()}大于\texttt{vec.len()}时尝试释放额外的内存。}

\texttt{Vec<T>}有很多添加或移除元素的方法，同时改变vector的长度。所有这些方法都以\texttt{mut}引用获取\texttt{self}参数。

下面这两个方法在vector的末尾添加或移除一个元素：

\codeentry{vec.push(value)}
\hangparagraph{把\texttt{value}添加到\texttt{vec}的末尾。}

\codeentry{vec.pop()}
\hangparagraph{移除并返回最后一个元素。返回类型是\texttt{Option<T>}。当vector已经为空时返回\texttt{None}，否则返回\texttt{Some(x)}。}

注意\texttt{.push()}以值而不是以引用获取参数。类似的，\texttt{.pop()}返回被弹出的值，而不是引用。本节中剩余的大部分方法也是这样。它们从vector移出或移进值。

这两个方法向vector中添加值或者从vector中移出值：
\codeentry{vec.insert(index, value)}
\hangparagraph{在\texttt{vec[index]}处插入给定的\texttt{value}，把\texttt{vec[index..]}中的值都向后移动一个位置来腾出空间。如果\texttt{index > vec.len()}会panic。}

\codeentry{vec.remove(index)}
\hangparagraph{移除并返回\texttt{vec[index]}，把\texttt{vec[index+1..]}中的值向左移动一个位置来消除缝隙。}

\texttt{.insert()}和\texttt{.remove()}都很慢，因为有很多元素需要移动。

有四个方法可以将vector的长度调整为指定值：

\codeentry{vec.resize(new\_len, value)}
\hangparagraph{将\texttt{vec}的长度设为\texttt{new\_len}。如果这会增大\texttt{vec}的长度，将会用\texttt{value}的拷贝填充新空间。元素的类型必须实现了\texttt{Clone} trait。}

\codeentry{vec.resize\_with(new\_len, closure)}
\hangparagraph{类似于\texttt{vec.resize}，但调用闭包来构造每一个新元素。它可以用于元素没有实现\texttt{Clone}的vector。}

\codeentry{vec.truncate(new\_len)}
\hangparagraph{将\texttt{vec}的长度缩减到\texttt{new\_len}，丢弃\texttt{vec[new\_len..]}范围内的所有元素。若\texttt{vec.len()}小于等于\texttt{new\_len}，则什么也不做。}

\codeentry{vec.clear()}
\hangparagraph{删除\texttt{vec}的所有元素。等价于\texttt{vec.truncate(0)}。}

有四个方法可以一次添加或移除很多元素：

\codeentry{vec.extend(iterable)}
\hangparagraph{将\texttt{iterable}的所有item按顺序添加到\texttt{vec}的末尾。它类似于多值版本的\texttt{.push()}。\texttt{iterable}参数可以是任何实现了\texttt{IntoIterator<Item=T>}。}

\hangparagraph{这个方法如此有用以至于有一个专门的trait \texttt{Extend}，所有的标准集合都实现了它。不幸的是，这导致\texttt{rustdoc}将\texttt{.extend()}和其他trait的方法放在生成的HTML底部的一堆方法中，因此当你需要它时很难找到它。你必须记住它！更多内容见\nameref{extend}。}

\codeentry{vec.split\_off(index)}
\hangparagraph{类似于\texttt{vec.truncate(index)}，除了它返回一个\texttt{Vec<T>}包含\texttt{vec}尾部被移除的元素。它类似于\texttt{.pop()}的多值版本。}

\codeentry{vec.append(\&mut vec2)}
\hangparagraph{这会把\texttt{vec2}的所有元素移动进\texttt{vec}，其中\texttt{vec2}是另一个\texttt{Vec<T>}类型的vector。调用之后，\texttt{vec2}变为空。}

\hangparagraph{这类似于\texttt{vec.extend(vec2)}，除了调用之后\texttt{vec2}仍然存在，并且容量不变。}

\codeentry{vec.drain(range)}
\hangparagraph{这会从\texttt{vec}中移除范围\texttt{vec[range]}，并返回一个迭代被移除元素的迭代器，其中\texttt{range}是一个范围值，例如\texttt{..}或\texttt{0..4}。}

还有一些选择性移除vector元素的古怪方法：
\codeentry{vec.retain(test)}
\hangparagraph{移除所有没有通过给定测试的方法。\texttt{test}参数是一个实现了\texttt{FnMut(\&T) -> bool}的函数或闭包。对于\texttt{vec}的每一个元素，它会调用\texttt{test(\&element)}，如果返回\texttt{false}，元素将会被移出vector然后丢弃。}

\hangparagraph{不考虑性能的话，这类似于：}
\begin{minted}{Rust}
    vec = vec.into_iter().filter(test).collect();
\end{minted}

\codeentry{vec.dedup()}
\hangparagraph{丢弃相邻的重复元素。它类似于Unix的\texttt{uniq} shell工具。它会扫描\texttt{vec}中寻找相邻的重复元素，然后丢弃掉多余的重复值，只留下一个：}
\begin{minted}{Rust}
    let mut byte_vec = b"Missssssissippi".to_vec();
    byte_vec.dedup();
    assert_eq!(&byte_vec, b"Misisipi");
\end{minted}
\hangparagraph{注意最后的输出中仍然有两个\texttt{'s'}字符。这个方法只移除\emph{相邻的(adjacent)}重复值。为了移除所有的重复值，你有三种选择：调用\texttt{.dedup()}之前先排序vector，将数据移动到一个\nameref{set}，或者（为了保持元素原本的顺序）使用这个\texttt{.retain()}技巧：}
\begin{minted}{Rust}
    let mut byte_vec = b"Missssssissippi".to_vec();

    let mut seen = HashSet::new();
    byte_vec.retain(|r| seen.insert(*r));

    assert_eq!(&byte_vec, b"Misp");
\end{minted}
\hangparagraph{这段代码的原理是当集合中已经包含要插入的item时\texttt{.insert()}会返回\texttt{false}。}

\codeentry{vec.dedup\_by(same)}
\hangparagraph{类似于\texttt{vec.dedup()}，但它使用函数或者闭包\texttt{same(\&mut elem1, \&mut elem2)}，而不是\texttt{==}运算符，来检查两个相邻元素是否被认为相等。}

\codeentry{vec.dedup\_by\_key(key)}
\hangparagraph{类似于\texttt{vec.dedup()}，但当\texttt{key(\&mut elem1) == key(\&mut elem2)}时它认为两个元素相等。}

\hangparagraph{例如，如果\texttt{errors}是一个\texttt{Vec<Box<dyn Error>>}，你可以写：}
\begin{minted}{Rust}
    // 移除消息重复的错误。
    errors.dedup_by_key(|err| err.to_string());
\end{minted}

这一节介绍的所有方法中，只有\texttt{.resize()}可能会拷贝值。其他的通过移动值来工作。

\subsection{连接}
两个方法可以用于\emph{数组的数组(array of array)}，即元素类型是数组、切片、vector的数组、切片、vector：

\codeentry{slices.concat()}
\hangparagraph{返回一个所有切片连接成的vector：}
\begin{minted}{Rust}
    assert_eq!([[1, 2], [3, 4], [5, 6]].concat(),
               vec![1, 2, 3, 4, 5, 6]);
\end{minted}

\codeentry{slices.join(\&separator)}
\hangparagraph{同上，除了会在切片之间插入\texttt{separator}的拷贝：}
\begin{minted}{Rust}
    assert_eq!([[1, 2], [3, 4], [5, 6]].join(&0),
               vec![1, 2, 0, 3, 4, 0, 5, 6]);
\end{minted}

\subsection{切分}\label{split}
很容易一次获得数组、切片、vector中的很多元素的非\texttt{mut}引用：
\begin{minted}{Rust}
    let v = vec![0, 1, 2, 3];
    let a = &v[i];
    let b = &v[j];

    let mid = v.len() / 2;
    let front_half = &v[..mid];
    let back_half = &v[mid..];
\end{minted}

但一次获得多个\texttt{mut}引用不是这么容易：
\begin{minted}{Rust}
    let mut v = vec![0, 1, 2, 3];
    let a = &mut v[i];
    let b = &mut v[j];  // error: 不能同时借用`v`的
                        // 多个可变引用。

    *a = 6;             // 引用`a`和`b`在这里使用了，
    *b = 7;             // 因此它们的生命周期一定会重叠。
\end{minted}

Rust禁止这样，因为如果\texttt{i == j}，那么\texttt{a}和\texttt{b}将是同一个整数的两个\texttt{mut}引用，这违背了Rust的安全性的规则。（见\nameref{ShareVSMut}）。

Rust有几个方法可以一次借用数组、切片、vector的两个或更多元素的\texttt{mut}引用。和上面的代码不同，这些方法是安全的，因为它们从设计上保证了只会把数组分割成\emph{非重叠(nonoverlapping)区域}。这些方法也可以用于非\texttt{mut}切片，因此它们有\texttt{mut}和非\texttt{mut}版本。

\hyperref[f16-2]{图16-2}展示了这些方法。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/f16-2.png}
    \caption{分割方法展示（注意：\texttt{slice.split()}输出中的小矩形是空的切片，因为两侧都是分隔符，\texttt{rsplitn}的输出是按照从后往前的顺序，这一点和其他的不同）。}
    \label{f16-2}
\end{figure}

这些方法中没有一个会直接修改数组、切片或vector，它们都返回部分数据的引用：
\codeentry{slice.iter(), slice.iter\_mut()}
\hangparagraph{产生\texttt{slice}的每个元素的引用。我们在\nameref{Iteration}中已经介绍过它们。}

\codeentry{slice.split\_at(index), slice.split\_at\_mut(index)}
\hangparagraph{把切片分成两半，返回一个pair。\texttt{slice.split\_at(index)}等价于\texttt{(\&slice[..index], \&slice[index..])}。如果\texttt{index}越界会panic。}

\codeentry{slice.split\_first(), slice.split\_first\_mut()}
\hangparagraph{返回一个pair：第一个元素的引用(\texttt{slice[0]})和其余所有元素的切片(\texttt{slice[1..]})。}

\hangparagraph{\texttt{.spilt\_first()}的返回值类型是\texttt{Option<(\&T, \&[T])>}；如果\texttt{slice}为空，返回\texttt{None}。}

\codeentry{slice.split\_last(), slice.split\_last\_mut()}
\hangparagraph{类似上一个，不过划分出最后一个元素而不是第一个。}

\hangparagraph{\texttt{.split\_last()}的返回类型也是\texttt{Option<(\&T, \&[T])>}。}

\codeentry{slice.split(is\_sep), slice.split\_mut(is\_sep)}
\hangparagraph{将\texttt{slice}切分成一个或更多子切片，使用函数或闭包\texttt{is\_sep}来判断在哪里切分。它们返回一个迭代子切片的迭代器。}

\hangparagraph{当消耗迭代器时，它们会对切片中的每个元素调用\texttt{is\_sep(\&element)}。如果返回\texttt{true}，那么这个元素就是一个分隔符。分隔符不包含在任何输出的字切片中。}

\hangparagraph{输出总是包含至少一个子切片，每有一个分隔符就加一个子切片。如果有相邻的分隔符或者\texttt{slice}的两端是分隔符都会产生空的子切片。}

\codeentry{slice.rsplit(is\_sep), slice.rsplit\_mut(is\_sep)}
\hangparagraph{类似于\texttt{slice}和\texttt{slice\_mut}，但从最后一个切片开始。}

\codeentry{slice.splitn(n, is\_sep), slice.splitn\_mut(n, is\_sep)}
\hangparagraph{类似上面的方法，不过最多产生\texttt{n}个子切片。当发现了前\texttt{n-1}个切片之后就不会再调用\texttt{is\_sep}。最后一个子切片将包含剩余的所有元素。}

\codeentry{slice.rsplitn(n, is\_sep), slice.rsplitn\_mut(n, is\_sep)}
\hangparagraph{类似于\texttt{.splitn()}和\texttt{.splitn\_mut()}，除了反向扫描切片。就是说，这个方法会在切片中\emph{最后}\texttt{n-1}个分隔符处切分，而不是前\texttt{n-1}个，并且从尾部开始产生子切片。}

\codeentry{slice.chunks(n), slice.chunks\_mut(n)}
\hangparagraph{返回一个产生长度为\texttt{n}的非重叠子切片的迭代器。如果\texttt{n}不能整除\texttt{slice.len()}，最后一个块的元素数量将小于\texttt{n}。}

\codeentry{slice.rchunks(n), slick.rchunks\_mut(n)}
\hangparagraph{类似于\texttt{slice.chunks()}和\texttt{slice.chunks\_mut()}，但是从切片的尾部开始。}

\codeentry{slice.chunks\_exact(n), slice.chunks\_exact\_mut(n)}
\hangparagraph{返回一个产生长度为\texttt{n}的非重叠子切片的迭代器。如果\texttt{n}不能整除\texttt{slice.len()}，最后一个块(元素数量小于\texttt{n})可以通过结果的\texttt{remainder()}方法获得。}

\codeentry{slice.rchunks\_exact(n), slice.rchunks\_exact\_mut(n)}
\hangparagraph{类似于\texttt{slice.chunks\_exact}和\texttt{slice.chunks\_exact\_mut}，但从切片的尾部开始。}

还有一些其他迭代子切片的方法：
\codeentry{slice.windows(n)}
\hangparagraph{返回一个效果类似于“滑动窗口”的迭代器。它产生\texttt{slice}中相邻的\texttt{n}个元素的子切片。第一个产生的值是\texttt{\&slice[0..n]}，第二个是\texttt{\&slice[1..n+1]}，以此类推。}

\hangparagraph{如果\texttt{n}大于\texttt{slice}的长度，将不会产生切片。如果\texttt{n}是0，这个方法会panic。}

\hangparagraph{例如，如果\texttt{days.len() == 31}，那么我们可以调用\texttt{days.windows(7)}产生\texttt{days}中所有7天的区间。}

\hangparagraph{在探索数据列的变化趋势时一个大小为2的滑动窗口会很有用：}
\begin{minted}{Rust}
    let changes = daily_high_temperatures
                      .windows(2)           // 获得相邻天的温度
                      .map(|w| w[1] - w[0]) // 温度改变了多少
                      .collect::<Vec<_>>();
\end{minted}
\hangparagraph{因为子切片是重叠的，所以这个方法没有返回\texttt{mut}引用的版本。}

\subsection{交换}
有一些交换切片内容的便捷方法：

\codeentry{slice.swap(i, j)}
\hangparagraph{交换元素\texttt{slice[i]}和\texttt{slice[j]}。}

\codeentry{slice\_a.swap(\&mut slice\_b)}
\hangparagraph{交换\texttt{slice\_a}和\texttt{slice\_b}的全部内容。\texttt{slice\_a}和\texttt{slice\_b}长度必须相同。}

vector有一个高效地移除任何元素的方法：

\codeentry{vec.swap\_remove(i)}
\hangparagraph{移除并返回\texttt{vec[i]}。这类似于\texttt{vec.remove(i)}，除了它不是把剩余的元素往前移动来消除间隙，而是把\texttt{vec}的最后一个元素移动到间隙。当你不关心vector中元素的顺序时这很有用。}

\subsection{排序和搜索}
切片提供了三个用于排序的方法：

\codeentry{slice.sort()}
\hangparagraph{按增序排序元素。只有当元素类型实现了\texttt{Ord}，这个方法才可用。}

\codeentry{slice.sort\_by(cmp)}
\hangparagraph{使用函数或闭包\texttt{cmp}指定顺序来排序\texttt{slice}的元素。\texttt{cmp}必须实现了\texttt{Fn(\&T, \&T) -> std::cmp::Ordering}。}

\hangparagraph{手动实现\texttt{cmp}很麻烦，除非你用\texttt{.cmp}方法：}
\begin{minted}{Rust}
    students.sort_by(|a, b| a.last_name.cmp(&b.last_name));
\end{minted}
\hangparagraph{如果要先比较一个字段，再比较第二个字段，可以直接比较元组：}
\begin{minted}{Rust}
    students.sort_by(|a, b| {
        let a_key = (&a.last_name, &a.first_name);
        let b_key = (&b.last_name, &b.first_name);
        a_key.cmp(&b_key)
    });
\end{minted}

\codeentry{slice.sort\_by\_key(key)}
\hangparagraph{以给定的函数或闭包\texttt{key}作为排序键将\texttt{slice}的元素按照增序排序。\texttt{key}的类型必须实现了\texttt{Fn(\&T) -> K where K: Ord}}。
\hangparagraph{当\texttt{T}包含一个或更多有序字段时这很有用，因为它可以按照多种方式排序：}
\begin{minted}{Rust}
    // 按照平均绩点排序，低的靠前
    students.sort_by_key(|s| s.grade_point_average());
\end{minted}
\hangparagraph{注意这些排序键在排序过程中并不会被缓存，因此\texttt{key}函数可能会被调用超过\texttt{n}次。}

\hangparagraph{出于技术上的原因，\texttt{key(element)}不能返回任何从元素借用的引用。这样不能工作：}
\begin{minted}{Rust}
    students.sort_by_key(|s| &s.last_name); // 错误：无法推断生命周期
\end{minted}
\hangparagraph{Rust无法查明生命周期。但在这种情况下，可以调用\texttt{.sort\_by()}作为替代。}

这三种方法都是稳定性排序。

为了实现反向排序，你可以使用\texttt{sort\_by}，然后在\texttt{cmp}闭包中交换两个参数。将参数写为\texttt{|b, a|}而不是\texttt{|a, b|}可以高效地产生相反的顺序。或者你可以在排序之后调用\texttt{.reverse()}方法：

\codeentry{slice.reverse()}
\hangparagraph{反转一个切片。}

一旦一个切片被排过序，它就可以被高效地搜索：
\codeentry{slice.binary\_search(\&value), slice.binary\_search\_by(\&value, cmp), slice.binary\_search\_by\_key(\&value, key)}
\hangparagraph{这些方法都在有序的\texttt{slice}中搜索\texttt{value}。注意\texttt{value}是以引用传递。}

\hangparagraph{它们的返回类型都是\texttt{Result<usize, usize>}。如果\texttt{slice[index]}在指定的排序顺序下等于\texttt{value}它们会返回\texttt{Ok(index)}。如果没有这样的元素会返回\texttt{Err(insertion\_point)}，在\texttt{insertion\_point}处插入\texttt{value}将保持有序。}

当然，二分搜索只在切片在指定的顺序下有序时才能工作。否则，结果将是任意值——garbage in, garbage out。

因为\texttt{f32}和\texttt{f64}有NaN值，它们没有实现\texttt{Ord}，因此不能被直接用作排序或二分搜索的键。为了得到可以用于浮点数的类似方法，使用\texttt{ord\_subset} crate。

还有一个在无序vector中搜索元素的方法：

\codeentry{slice.contains(\&value)}
\hangparagraph{如果\texttt{slice}中有任何一个元素等于\texttt{value}则返回\texttt{true}。它简单地检查切片的每个元素，直到找到要查找的值。另外，\texttt{value}也是以引用传递。}

为了查找一个切片中某一个值的位置，类似于JavaScript中的\texttt{array.indexOf(value)}，使用迭代器：
\begin{minted}{Rust}
    slice.iter().position(|x| *x == value)
\end{minted}
这会返回\texttt{Option<usize>}。

\subsection{比较切片}
如果类型\texttt{T}支持\texttt{==}和\texttt{!=}运算符（\texttt{PartialEq} trait，见\nameref{equal}），那么数组\texttt{[T; N]}、切片\texttt{[T]}、vector \texttt{Vec<T>}也支持这些运算符。当两个切片的长度和相应的元素都相等时两个切片才相等。数组和vector也是一样。

如果\texttt{T}支持运算符\texttt{<}、\texttt{<=}、\texttt{>}、\texttt{>=}（\texttt{PartialOrd} trait，见\nameref{cmp}），那么\texttt{T}的数组、切片和vector也支持。切片的比较按照字典序进行。

有两个便捷的方法进行常用的切片比较：

\codeentry{slice.starts\_with(other)}
\hangparagraph{如果\texttt{slice}起始的值序列等于\texttt{other}的元素则返回\texttt{true}：}
\begin{minted}{Rust}
    assert_eq!([1, 2, 3, 4].starts_with(&[1, 2]), true);
    assert_eq!([1, 2, 3, 4].starts_with(&[2, 3]), false);
\end{minted}

\codeentry{slice.ends\_with(other)}
\hangparagraph{和上边类似但检查\texttt{slice}的末尾：}
\begin{minted}{Rust}
    assert_eq!([1, 2, 3, 4].ends_with(&[3, 4]), true);
\end{minted}

\subsection{随机元素}
Rust的标准库中并不包含随机数。\texttt{rand} crate提供了它们，还提供了两个方法从数组、切片、vector中获取随机元素：

\codeentry{slice.choose(\&mut rng)}
\hangparagraph{返回切片中随机一个元素的引用。类似于\texttt{slice.first()}和\texttt{slice.last()}，除了它返回一个\texttt{Option<\&T>}，如果切片为空，返回值为\texttt{None}。}

\codeentry{slice.shuffle(\&mut rng)}
\hangparagraph{随机打乱切片中的元素的顺序。切片必须以\texttt{mut}引用传递。}

这些是\texttt{rand::Rng} trait的方法，因此为了调用它们你需要一个\texttt{Rng}，它是一个随机数生成器。幸运的是，可以调用\texttt{rand::thread\_rng()}来获得一个。要想打乱vector \texttt{my\_vec}，你可以写：
\begin{minted}{Rust}
    use rand::seq::SliceRandom;
    use rand::thread_rng;

    my_vec.shuffle(&mut thread_rng());
\end{minted}

\subsection{Rust排除了无效性错误}
大多数主流编程语言都有集合和迭代器，而且都有这个规则的变体：不要在遍历集合的同时修改它。例如，Python中vecotr等价的是list：
\begin{minted}{Rust}
    my_list = [1, 3, 5, 7, 9]
\end{minted}

假设我们想移除\texttt{my\_list}中大于4的元素；
\begin{minted}{python}
    for index, val in enumerate(my_list):
        if val > 4:
            del my_list[index]  # bug: 在迭代的同时修改

    print(my_list)
\end{minted}
（Python中的\texttt{enumerate}函数等价于Rust中的\texttt{.enumerate()}方法，见\nameref{enumerate}。）

这个程序令人惊讶地打印出\texttt{[1, 3, 7]}。但7比4大，为什么它没被移除？这就是无效性错误：程序在迭代数据的同时修改它，将迭代器\emph{无效化(invalidate)}。在Java中，结果可能是一个异常；在C++中是未定义行为。而在Python中，这个行为是有定义的，虽然不太直观：
迭代器会跳过一个元素。\texttt{val}永远不会是\texttt{7}。

让我们尝试在Rust中复现这个bug：
\begin{minted}{Rust}
    fn main() {
        let mut my_vec = vec![1, 3, 5, 7, 9];

        for (index, &val) in my_vec.iter().enumerate() {
            if val > 4 {
                my_vec.remove(index);   // error: can't borrow `my_vec` as mutable
            }
        }
        println!("{:?}", my_vec);
    }
\end{minted}

Rust自然会在编译期拒绝这个程序。当我们调用\texttt{my\_vec.iter()}时，它借用了vector的一个共享（非\texttt{mut}）引用。引用的生命周期和迭代器一样长，也就是直到\texttt{for}循环的结尾。我们不能在有非\texttt{mut}引用存在时调用\texttt{my\_vec.remove(index)}修改vector。

编译器能指出这个错误非常好，但当然，你仍然需要一种方法来得到期望的行为！这里最简单的修复方法是：
\begin{minted}{Rust}
    my_vec.retain(|&val| val <= 4);
\end{minted}

或者，你可以采用在Python或其他任何语言中也可以实现的方法：使用\texttt{filter}来创建一个新的vector。

\section{\texttt{VecDeque<T>}}

\texttt{Vec}只支持在尾部高效地添加和删除元素。当一个程序需要存储“排队”的值时，\texttt{Vec}会变得很慢。

Rust的集合\texttt{std::collections::VecDeque<T>}是一个\emph{双端队列(deque)}（读作“deck”）。它支持在头部和尾部高效地添加和移除元素：

\codeentry{deque.push\_front(value)}
\hangparagraph{在队列的头部添加一个值。}

\codeentry{deque.push\_back(value)}
\hangparagraph{在尾部添加一个值。（这个方法比\texttt{.push\_front()}用得更多，因为队列的通常用法是从尾部添加并从头部移除，就像人在排队一样。）}

\codeentry{deque.pop\_front()}
\hangparagraph{移除并返回队列头部的值，返回\texttt{Option<T>}，如果队列为空则返回\texttt{None}，类似于\texttt{vec.pop()}。}

\codeentry{deque.pop\_back()}
\hangparagraph{移除并返回尾部的元素，同样返回\texttt{Option<T>}。}

\codeentry{deque.front(), deque.back()}
\hangparagraph{类似于\texttt{vec.first()}和\texttt{vec.last()}。它们返回队列中头部或者尾部元素的引用。返回类型是\texttt{Option<\&T>}，当队列为空时返回\texttt{None}。}

\codeentry{deque.front\_mut(), deque.back\_mut()}
\hangparagraph{类似于\texttt{vec.first\_mut()}和\texttt{vec.last\_mut()}，返回\texttt{Option<\&mut T>}}。

\texttt{VecDeque}的实现是一个环形缓冲区，如\hyperref[f16-3]{图16-3}所示。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/f16-3.png}
    \caption{\texttt{VecDeque}在内存中如何存储}
    \label{f16-3}
\end{figure}

类似于\texttt{Vec}，它有一个堆上分配的缓冲区用来存储元素。和\texttt{Vec}不同的是，数据并不总是从区域的起点开始存储，并且可以在结尾处“回环”。图中这个队列的元素，按顺序分别是\texttt{['A', 'B', 'C', 'D', 'E']}。\texttt{VecDeque}有私有的字段标记图中的\texttt{start}和\texttt{stop}，用来记录缓冲区中数据的起点和终点。

向队列首部或者尾部添加值，意味着要占用一个未使用的位置（图中颜色较深的块），如果需要的话可能会回环或者分配更大的内存块。

\texttt{VecDeque}负责管理回环，因此你不需要考虑它。\hyperref[f16-3]{图16-3}是Rust保证\texttt{.pop\_front()}速度很快的幕后视图。

很多时候，当你需要双端队列的时候，你可能只需要\texttt{.push\_back()}和\texttt{.pop\_front()}两个方法。类型关联函数\texttt{VecDeque::new()}和\texttt{VecDeque::with\_capacity(n)}用于创建队列，类似于\texttt{Vec}的相应函数。很多\texttt{Vec}的方法在\texttt{VecDeque}中都有实现：\texttt{.len(), .is\_empty(), .insert(index, value), .remove(index), .extend(iterable)}，等等。

双端队列和vector一样可以以值、以共享引用或者以\texttt{mut}引用迭代。它们都有三个迭代器方法\texttt{.into\_iter(), .iter(), .iter\_mut()}。它可以用通常的方式索引：\texttt{deque[index]}。

因为双端队列在内存中并不是连续存储元素，因此它不能继承切片的方法。但如果你愿意承受移动元素的开销，\texttt{VecDeque}提供了一个方法来修复它：

\codeentry{deque.make\_contiguous()}
\hangparagraph{以\texttt{\&mut self}为参数，把\texttt{VecDeque}重新排布到连续的内存中，返回\texttt{\&mut [T]}。}

\texttt{Vec}和\texttt{VecDeque}高度相关，标准库提供了两个trait实现来轻松地互相转换：

\codeentry{Vec::from(deque)}
\hangparagraph{\texttt{Vec<T>}实现了\texttt{From<VecDeque<T>>}，因此这会把一个双端队列变成一个vector。这会消耗O(n)时间，因为它可能要重新排布元素。}

\codeentry{VecDeque::from(vec)}
\hangparagraph{\texttt{VecDeque<T>}实现了\texttt{From<Vec<T>>}，因此这会把一个vector转换成一个双端队列。这也是O(n)复杂度，但它通常会很快，即使vector很大，因为vector的堆缓冲区可以简单地移动到新的双端队列中。}

\hangparagraph{它可以让我们简单地用指定元素创建一个双端队列，即使没有标准的\texttt{vec\_deque![]}宏：}
\begin{minted}{Rust}
    use std::collections::VecDeque;

    let v = VecDeque::from(vec![1, 2, 3, 4]);
\end{minted}

\section{\texttt{BinaryHeap<T>}}

\texttt{BinaryHeap<T>}集合始终以某种形式组织元素，其中最大的元素总是会被移动到队列的首部。这里是\texttt{BinaryHeap}最常用的几个方法：

\codeentry{heap.push(value)}
\hangparagraph{向堆中添加一个元素}

\codeentry{heap.pop()}
\hangparagraph{移除并返回堆中最大的值。它返回\texttt{Option<T>}，如果堆为空时返回\texttt{None}。}

\codeentry{heap.peek()}
\hangparagraph{返回堆中最大的值的引用。返回类型是\texttt{Option<\&T>}。}

\codeentry{heap.peek\_mut()}
\hangparagraph{返回一个\texttt{PeekMut<T>}，它可以用作堆中最大值的一个可变引用，并提供类型关联函数\texttt{pop()}来从堆中弹出这个值。使用这个方法，我们可以根据最大的元素的值来决定要不要从堆中弹出这个元素：}
\begin{minted}{Rust}
    use std::collections::binary_heap::PeekMut;

    if let Some(top) = heap.peek_mut() {
        if *top > 10 {
            PeekMut::pop(top);
        }
    }
\end{minted}

\texttt{BinaryHeap}支持\texttt{Vec}的方法的一个子集，包括\texttt{BinaryHeap::new(), .len(), .is\_empty(), .capacity(), .clear(), .append(\&mut heap2)。}

例如，假设我们用一些数字填充一个\texttt{BinaryHeap}：
\begin{minted}{Rust}
    use std::collections::BinaryHeap;

    let mut heap = BinaryHeap::from(vec![2, 3, 8, 6, 9, 5, 4]);
\end{minted}

值\texttt{9}在堆的顶部：
\begin{minted}{Rust}
    assert_eq!(heap.peek(), Some(&9));
    assert_eq!(heap.pop(), Some(9));
\end{minted}

移除\texttt{9}也会重新排布其他元素，把\texttt{8}移动到头部，等等：
\begin{minted}{Rust}
    assert_eq!(heap.pop(), Some(8));
    assert_eq!(heap.pop(), Some(6));
    assert_eq!(heap.pop(), Some(5));
    ...
\end{minted}

当然，\texttt{BinaryHeap}并不仅限于数字。它可以包含任何实现了内建的\texttt{Ord} trait的类型。

这让\texttt{BinaryHeap}可以用作一个工作队列。你可以定义一个任务结构体，然后根据任务的优先级实现\texttt{Ord}，让高优先级的任务大于低优先级的任务。然后，创建一个\texttt{BinaryHeap}来保存所有待办的任务。它的\texttt{.pop()}方法将总是返回最重要的任务。

注意：\texttt{BinaryHeap}是可迭代的对象，并且它有\texttt{.iter()}方法，但这个迭代器以任意顺序产生堆中的元素，而不是按照从大到小的顺序。为了按照大小顺序消耗\texttt{BinaryHeap}中的值，可以使用\texttt{while}循环：
\begin{minted}{Rust}
    while let Some(task) = heap.pop() {
        handle(task);
    }
\end{minted}

\section{\texttt{HashMap<K, V>}和\texttt{BTreeMap<K, V>}}

\emph{map(映射)}是键值对（称为\emph{条目(entry)}）的集合。任何两个条目的键都不同，所有的条目按照一定结构组织，如果有一个键就可以高效地在map中查找到相应的值。简而言之，map是一个查找表。

Rust提供两者两种map类型：\texttt{HashMap<K, V>}和\texttt{BTreeMap<K, V>}。这两种类型共享了很多相同的方法；不同之处在于它们组织条目的方式。

\texttt{HashMap}把键和值都存储在哈希表中，因此它要求键的类型\texttt{K}实现了\texttt{Hash}和\texttt{Eq}，这两个trait分别用于哈希和相等性比较。

\hyperref[f16-4]{图16-4}展示了\texttt{HashMap}如何在内存中排布。深色区域表示没有使用。所有的键、值和缓存的哈希值都被存储在单个堆上分配的表中。添加条目最终会迫使\texttt{HashMap}分配更大的表，并把所有数据移动进去。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.9\textwidth]{../img/f16-4.png}
    \caption{\texttt{HashMap}的内存布局}
    \label{f16-4}
\end{figure}

\texttt{BTreeMap}按照键的顺序在树形结构中存储条目，因此它要求键的类型\texttt{K}实现了\texttt{Ord}。\hyperref[f16-5]{图16-5}展示了一个\texttt{BTreeMap}。同样，深色区域表示没有被使用的空间。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{../img/f16-5.png}
    \caption{\texttt{BTreeMap}的内存布局}
    \label{f16-5}
\end{figure}

\texttt{BTreeMap}把条目存储在\emph{节点(node)}中。一个\texttt{BTreeMap}中大多数的节点都只包含键值对。而非叶节点，例如图中所示的根节点，还需要存储指向子节点的指针。\texttt{(20, 'q')}和\texttt{(30, 'r')}之间的指针指向包含\texttt{20}和\texttt{30}之间的键的子节点。添加条目通常需要把某个节点的部分现有条目向右移动，来保持它们有序，有时还需要分配新的节点。

图中的示例经过简化来适应页面。例如，实际的\texttt{BTreeMap}节点有11个条目的空间，而不是\texttt{4}个。

Rust标准库使用B树而不是二叉平衡树，因为在现代硬件上B树更快。查找时二叉树可能比B树的比较次数更少，但在B树中查找有更好的\emph{局部性(locality)}——即，内存被成组访问，而不是扫描整个堆。这让CPU缓存的命中率更高，这能显著地提高速度。

这里有几种创建map的方法：

\codeentry{HashMap::new(), BTreeMap::new()}
\hangparagraph{创建新的空map。}

\codeentry{iter.collect()}
\hangparagraph{从键值对创建并填充新的\texttt{HashMap}或\texttt{BTreeMap}。\texttt{iter}必须是一个\texttt{Iterator<Item=(K, V)>}。}

\codeentry{HashMap::with\_capacity(n)}
\hangparagraph{创建一个新的空哈希表，并分配至少能存储\texttt{n}个条目的空间。\texttt{HashMap}和vector一样把数据存储在单个堆上的内存中，因此它也有容量以及相关的方法\texttt{hash\_map.capacity(), \texttt{hash\_map.reserve(additional)}, hash\_map.shrink\_to\_fit()}。\texttt{BTreeMap}则没有。}

\texttt{HashMap}和\texttt{BTreeMap}有相同的处理键和值的核心方法：

\codeentry{map.len()}
\hangparagraph{返回条目的数量。}

\codeentry{map.is\_empty()}
\hangparagraph{返回\texttt{map}里是否没有条目}

\codeentry{map.contains\_key(\&key)}
\hangparagraph{如果\texttt{map}里有给定\texttt{key}的条目则返回\texttt{true}。}

\codeentry{map.get(\&key)}
\hangparagraph{在\texttt{map}中查找给定\texttt{key}的条目。如果找到了匹配的条目，就返回\texttt{Some(r)}，其中\texttt{r}是相应的值的引用。否则返回\texttt{None}。}

\codeentry{map.get\_mut(\&key)}
\hangparagraph{与上面类似，但返回值的\texttt{mut}引用。}

\hangparagraph{一般来讲，map让你可以获取值的\texttt{mut}访问能力，但不能获取键的\texttt{mut}访问。值属于你，你可以随意修改它。但键术语map本身，它需要保证键不会改变，因为条目按照键来组织。原地修改键将会导致bug。}

\codeentry{map.insert(key, value)}
\hangparagraph{向\texttt{map}中插入条目\texttt{(key, value)}，并返回旧的值（如果有的话）。返回类型是\texttt{Option<V>}，如果map中已经有了\texttt{key}的条目，那么新插入的\texttt{value}会覆盖旧值。}

\codeentry{map.extend(iterable)}
\hangparagraph{迭代\texttt{iterable}中的\texttt{(K, V)} item，并把每一个键值对插入\texttt{map}。}

\codeentry{map.append(\&mut map2)}
\hangparagraph{把\texttt{map2}中的所有条目移动到\texttt{map}中。完成之后，\texttt{map2}变为空。}

\codeentry{map.remove(\&key)}
\hangparagraph{查找并移除\texttt{map}中给定的\texttt{key}的条目，返回被移除的值（如果有的话）。返回类型是\texttt{Option<V>}。}

\codeentry{map.remove\_entry(\&key)}
\hangparagraph{查找并移除\texttt{map}中给定的\texttt{key}的条目，返回被移除的键和值（如果有的话）。返回类型是\texttt{Option<(K, V)>}。}

\codeentry{map.retain(test)}
\hangparagraph{移除所有未通过测试的元素。参数\texttt{test}参数是一个实现了\texttt{FnMut(\&K, \&mut V) -> bool}的函数或者闭包。它会对\texttt{map}中的每一个元素调用\texttt{test(\&key, \&mut value)}，如果返回\texttt{false}，就移除掉这个元素并丢弃。}

\hangparagraph{不考虑性能的话，这类似于如下写法：}
\begin{minted}{Rust}
    map = map.into_iter().filter(test).collect();
\end{minted}

\codeentry{map.clear()}
\hangparagraph{移除所有元素。}

map可以使用方括号\texttt{map[\&key]}进行查询。这是因为map实现了内建的\texttt{Index} trait。然而，如果没有给定的\texttt{key}的条目存在，这会panic，就类似越界访问数组一样。因此只有当你确定要查找的条目在map中时再使用这个语法。

\texttt{.contains\_key(), .get(), .get\_mut(), .remove()}方法的\texttt{key}参数的类型不一定要是精确的\texttt{\&K}。这些方法都是泛型方法，只要能从\texttt{K}类型借用参数的类型的引用即可。假设\texttt{fish\_map}是一个\texttt{HashMap<String, Fish>}，那么即使\texttt{"conger"}并不是\texttt{String}，我们也可以调用\texttt{fish\_map.contains\_key("conger")}，。因为\texttt{String}实现了\texttt{Borrow<\&str>}，所以可以从\texttt{String}借用一个\texttt{\&str}。详情见\nameref{borrow}。

因为一个\texttt{BTreeMap<K, V>}按照键的顺序保存条目，所以它支持一个附加的操作：
\codeentry{btree\_map.split\_off(\&key)}
\hangparagraph{把\texttt{btree\_map}分割成两个。键小于\texttt{key}的条目被留在\texttt{btree\_map}中，返回一个包含其余条目的新\texttt{BTreeMap<K, V>}。}

\subsection{条目}\label{entry}
\texttt{HashMap}和\texttt{BTreeMap}都有相应的\texttt{Entry}类型。这个类型的意义是避免重复的查找。例如，这里有一些代码获取或者创建一个学生的记录：
\begin{minted}{Rust}
    // 我们已经有了这名学生的记录了吗？
    if !student_map.contains_key(name) {
        // 没有：创建一条记录
        student_map.insert(name.to_string(), Student::new());
    }
    // 现在确定这条记录肯定存在了。
    let record = student_map.get_mut(name).unwrap();
    ...
\end{minted}

这可以正常工作，但它访问了\texttt{student\_map}两次或者三次，每次都做相同的查找。

条目的思路是我们只查找一次，产生一个\texttt{Entry}值，然后后续的操作都通过它进行。下面的单行代码等于上面的所有代码，除了它只查找一次：
\begin{minted}{Rust}
    let record = student_map.entry(name.to_string()).or_insert_with(Student::new);
\end{minted}

\texttt{student\_map.entry(name.to\_string())}返回的\texttt{Entry}值就像一个可变引用，它指向map中一个已经被键值对\emph{占据(occupied)}的位置，或者是\emph{空的(vacant)}，意思是还没有条目占据这个位置。如果为空，条目的\texttt{.or\_insert\_with()}方法会插入一个新的\texttt{Student}。条目的大多数使用都类似这样：简短而方便。

所有的\texttt{Entry}值都只能用同一个方法创建：
\codeentry{map.entry(key)}
\hangparagraph{对给定的\texttt{key}返回一个\texttt{Entry}。如果map中没有这个key，它会返回一个空的\texttt{Entry}。}

\hangparagraph{这个方法以\texttt{mut}引用获取\texttt{self}参数，并返回一个生命周期相同的\texttt{Entry}：}
\begin{minted}{Rust}
    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
\end{minted}
\hangparagraph{\texttt{Entry}类型有一个生命周期参数\texttt{'a}，因为它是map的一种\texttt{mut}借用。只要\texttt{Entry}存在，它就有map的独占访问权限。}

\hangparagraph{回顾\nameref{refstruct}，我们看到过如何在一个类型中存储引用以及这样对生命周期的影响。现在我们从用户的视角看看它是什么样的。也正是\texttt{Entry}的情况。}

\hangparagraph{不幸的是，如果map的键的类型为\texttt{String}，那么不能向这个方法传递\texttt{\&str}类型的参数。这种情况下的\texttt{.entry()}方法需要一个真实的\texttt{String}。}

\texttt{Entry}值提供了三个处理空条目的方法：

\codeentry{map.entry(key).or\_insert(value)}
\hangparagraph{确保\texttt{map}包含给定的\texttt{key}的条目，如果需要的话用给定的\texttt{value}插入一个新的条目。它返回新插入的或者现有的值的\texttt{mut}引用。}

\hangparagraph{假设我们需要计数投票。我们可以写：}
\begin{minted}{Rust}
    let mut vote_counts: HashMap<String, usize> = HashMap::new();
    for name in ballots {
        let count = vote_counts.entry(name).or_insert(0);
        *count += 1;
    }
\end{minted}
\hangparagraph{\texttt{.or\_insert()}返回一个可变引用，因此\texttt{count}的类型是\texttt{\&mut usize}。}

\codeentry{map.entry(key).or\_default()}
\hangparagraph{确保\texttt{map}包含给定的\texttt{key}的条目，如果需要的话用\texttt{Default::default()}返回的值插入一个新条目。只有当值的类型实现了\texttt{Default}时这个方法才能工作。类似于\texttt{or\_insert}，这个方法返回新插入的或者现有的值的\texttt{mut}引用。}

\codeentry{map.entry(key).or\_insert\_with(default\_fn)}
\hangparagraph{这个方法也一样，除了当它需要创建新的条目时，它会调用\texttt{default\_fn()}来产生默认值。如果\texttt{map}中已经有了\texttt{key}的条目，那么\texttt{default\_fn}将不会被调用。}

\hangparagraph{假设我们想知道哪个单词在哪个文件中出现。我们可以写：}
\begin{minted}{Rust}
    // 这个map中包含每个单词和出现它的文件的集合。
    let mut word_occurrence: HashMap<String, HashSet<String>> = HashMap::new();
    for file in files {
        for word in read_words(file)? {
            let set = word_occurrence
                .entry(word)
                .or_insert_with(HashSet::new);
            set.insert(file.clone());
        }
    }
\end{minted}

\texttt{Entry}还提供了一个只修改现存条目的便捷方法。

\codeentry{map.entry(key).and\_modify(closure)}
\hangparagraph{如果给定的\texttt{key}的条目存在就调用\texttt{closure}，把值的可变引用传进闭包。它返回一个\texttt{Entry}，因此它可以和其它方法链式调用。}

\hangparagraph{例如，我们可以使用它来统计一个字符串中每个单词出现的次数：}
\begin{minted}{Rust}
    // 这个map包含给定字符串中的所有单词，
    // 以及它们出现的次数。
    let mut word_frequency: HashMap<&str, u32> = HashMap::new();
    for c in text.split_whitespace() {
        word_frequency.entry(c)
            .and_modify(|count| *count += 1)
            .or_insert(1);
    }
\end{minted}

\texttt{Entry}类型是一个枚举，\texttt{HashMap}的\texttt{Entry}定义类似于这样（\texttt{BTreeMap}的\texttt{Entry}类似）：
\begin{minted}{Rust}
    // (in std::collections::hash_map)
    pub enum Entry<'a, K, V> {
        Occupied(OccupiedEntry<'a, K, V>),
        Vacant(VacantEntry<'a, K, V>)
    }
\end{minted}

\texttt{OccupiedEntry}和\texttt{VacantEntry}类型的方法用于在不需要重复查找的情况下插入、移除和访问条目。你可以在在线文档中找到它们。偶尔可以使用这些附加的方法来减少一次或两次查找，但\texttt{.or\_insert()}和\texttt{.or\_insert\_with()}就能覆盖大多数的情况。

\subsection{迭代map}
有几种迭代map的方法：
\begin{enumerate}
    \item 以值迭代(\texttt{for (k, v) in map})，产生\texttt{(K, V)}对。这会消耗掉map。
    \item 迭代共享引用(\texttt{for (k, v) in \&map})，产生\texttt{(\&K, \&V)}对。
    \item 迭代可变引用(\texttt{for (k, v) in \&mut})，产生\texttt{(\&K, \&mut V)}对。（再提醒一次，没有获取map中键的\texttt{mut}访问的方法，因为条目是按照键来组织的。
\end{enumerate}

类似于vector，map有\texttt{.iter()}和\texttt{.iter\_mut()}方法返回以引用迭代的迭代器，就类似于迭代\texttt{\&map}或者\texttt{\&mut map}。另外：

\codeentry{map.keys()}
\hangparagraph{返回一个只迭代键的迭代器，以引用的形式返回。}

\codeentry{map.values()}
\hangparagraph{返回一个只迭代值的迭代器，以引用的形式返回。}

\codeentry{map.values\_mut()}
\hangparagraph{返回一个只迭代值的迭代器，以\texttt{mut}引用的形式返回。}

所有的\texttt{HashMap}迭代器都会以任意顺序访问map的条目。\texttt{BTreeMap}的迭代器会按照键的顺序访问它们。

\section{\texttt{HashSet<T>}和\texttt{BTreeSet<T>}}\label{set}

\emph{set}是值的集合，它可以快速地测试元素：
\begin{minted}{Rust}
    let b1 = large_vector.contains(&"needle");      // 很慢，检查每一个元素
    let b2 = large_hash_set.contains(&"needle");    // 很快，哈希查找
\end{minted}

一个set绝不会包含同一个值的多个拷贝。

map和set有不同的方法，但其实一个set就是一个只有键而不是键值对的map。事实上，Rust的\texttt{HashSet<T>}和\texttt{BTreeSet<T>}被实现为\texttt{HashMap<T, ()>}和\texttt{BTreeMap<T, ()>}的包装。

\codeentry{HashSet::new(), BTreeSet::new()}
\hangparagraph{创建新的set。}

\codeentry{iter.collect()}
\hangparagraph{可以用于从任何迭代器创建set。如果\texttt{iter}产生某个值不止一次，那么重复的值将会被丢弃。}

\codeentry{HashSet::with\_capacity(n)}
\hangparagraph{创建一个空的\texttt{HashSet}，有至少能存储\texttt{n}个元素的空间。}

\texttt{HashSet<T>}和\texttt{BTreeSet<T>}有相同的公共基础方法：

\codeentry{set.len()}
\hangparagraph{返回set中值的数量。}

\codeentry{set.is\_empty()}
\hangparagraph{如果set不包含任何元素则返回\texttt{true}。}

\codeentry{set.contains(\&value)}
\hangparagraph{如果set包含给定的\texttt{value}则返回\texttt{true}。}

\codeentry{set.insert(value)}
\hangparagraph{向set中添加一个\texttt{value}。如果添加了值则返回\texttt{true}，如果set中已经有这个值了则返回\texttt{false}。}

\codeentry{set.remove(\&value)}
\hangparagraph{从set中删除\texttt{value}。如果有值被删除则返回\texttt{true}，如果没有这个值则返回\texttt{false}。}

\codeentry{set.retain(test)}
\hangparagraph{删除没有通过测试的元素。\texttt{test}参数是一个实现了\texttt{FnMut(\&T) -> bool}的函数或者闭包。对于\texttt{set}的每一个元素，都会调用\texttt{test(\&value)}，如果返回\texttt{false}，这个元素就会从set中删除，并且被丢弃。}

\hangparagraph{不考虑性能的话，这类似于：}
\begin{minted}{Rust}
    set = set.into_iter().filter(test).collect();
\end{minted}

和map一样，通过引用查找值的方法接受任何可以从\texttt{T}借用的类型。细节见\\
\nameref{borrow}。

\subsection{迭代set}
有两种迭代set的方法:
\begin{enumerate}
    \item 以值迭代(\texttt{for v in set})产生set的成员(并消耗这个set)。
    \item 以共享引用迭代(\texttt{for v in \&set})产生set中成员的共享引用。
\end{enumerate}

不支持以\texttt{mut}引用迭代set。没有方法获取set中值的\texttt{mut}引用。

\codeentry{set.iter()}
\hangparagraph{返回一个以共享引用方式迭代\texttt{set}的迭代器。}

\texttt{HashSet}迭代器类似于\texttt{HashMap}的迭代器，也会以任意顺序产生值。\texttt{BTreeSet}迭代器按照顺序产生值，类似于一个排序过的vector。

\subsection{当相等的值不同时}
set还有一些方法，只有当你关心“相等”值的差异时才会用到。

这样的差异经常出现。例如，两个完全相同的\texttt{String}值，在内存中的不同位置存储它们的字符：

\begin{minted}{Rust}
    let s1 = "hello".to_string();
    let s2 = "hello".to_string();
    println!("{:p}", &s1 as &str);  // 0x7f8b32060008
    println!("{:p}", &s2 as &str);  // 0x7f8b32060010
\end{minted}

通常我们并不会关心这些。

但在你需要的情况下，你可以使用下面的方法获得set中存储的值。这些方法都返回一个\texttt{Option}，当\texttt{set}不包含匹配的值时为\texttt{None}：

\codeentry{set.get(\&value)}
\hangparagraph{返回\texttt{set}中等于\texttt{value}的成员的共享引用，如果有的话。返回\texttt{Option<\&T>}。}

\codeentry{set.take(\&value)}
\hangparagraph{类似于\texttt{set.remove(\&value)}，但它会返回被删除的值，如果有的话。返回\texttt{Option<T>}。}

\codeentry{set.replace(value)}
\hangparagraph{类似于\texttt{set.insert(value)}，但如果\texttt{set}已经包含一个等于\texttt{value}的值，它会替换并返回旧的值。返回\texttt{Option<T>}。}

\subsection{集合操作}
到目前为止，我们看到的set方法都只关注单个set中的单个值。set还有一些操作整个集合的方法：

\codeentry{set1.intersection(\&set2)}
\hangparagraph{返回一个迭代器，迭代所有既在\texttt{set1}又在\texttt{set2}中的值。}

\hangparagraph{例如，如果我们想打印出所有同时选择了脑外科和火箭课程的学生的名字，我们可以写：}
\begin{minted}{Rust}
    for student in &brain_class {
        if rocket_class.contains(student) {
            println!("{}", student);
        }
    }
\end{minted}
\hangparagraph{或者，更短的写法：}
\begin{minted}{Rust}
    for student in brain_class.intersection(&rocket_class) {
        println!("{}", student);
    }
\end{minted}

令人惊奇的是，有专门的运算符来进行这种操作。

\texttt{\&set1 \& \&set2}返回一个新的set，它是\texttt{set1}和\texttt{set2}的交集。这是一元的按位AND运算符，用于两个引用。它会找到既在\texttt{set1}中又在\texttt{set2}中的值：
\begin{minted}{Rust}
    let overachievers = &brain_class & &rocket_class;
\end{minted}

\codeentry{set1.union(\&set2)}
\hangparagraph{返回一个迭代器，迭代要么在\texttt{set1}中要么在\texttt{set2}中的值。}

\hangparagraph{\texttt{\&set1 | \&set2}返回一个新的set，包含所有在\texttt{set1}\emph{或}\texttt{set2}中的值。}

\codeentry{set1.difference(\&set2)}
\hangparagraph{返回一个迭代器，迭代在\texttt{set1}中但不在\texttt{set2}中的值。}

\hangparagraph{\texttt{\&set1 - \&set2}返回一个新的set，包含所有这样的值。}

\codeentry{set1.symmetric\_difference(\&set2)}
\hangparagraph{返回一个迭代器，迭代\texttt{set1}或\texttt{set2}独有的值。}

\hangparagraph{\texttt{\&set1 \^{} \&set2}返回一个新的set，包含所有这样的值。}

还有三个方法用来测试两个set的关系：

\codeentry{set1.is\_disjoint(set2)}
\hangparagraph{如果\texttt{set1}和\texttt{set2}没有相同的元素则返回\texttt{true}——即它们的交集为空。}

\codeentry{set1.is\_subset(set2)}
\hangparagraph{如果\texttt{set1}是\texttt{set2}的子集则返回\texttt{true}——即\texttt{set1}中的所有值也都在\texttt{set2}。}

\codeentry{set1.is\_superset(set2)}
\hangparagraph{和上面相反，如果\texttt{set1}是\texttt{set2}的超集则返回true。}

set也支持使用\texttt{==}和\texttt{!=}进行相等性测试；如果两个set包含相同的值则它们相等。

\section{哈希}

\texttt{std::hash::Hash}是标准库用于可哈希类型的trait。\texttt{HashMap}的键和\texttt{HashSet}的元素必须实现了\texttt{Hash}和\texttt{Eq}。

大多数实现了\texttt{Eq}的内建类型也都实现了\texttt{Hash}。整数类型、\texttt{char}、\texttt{String}都是可哈希类型；当元素是可哈希类型时，元组、数组、切片、vector也是可哈希类型。

标准库的一个原则是不管你把一个值存储到哪里或者如何指向它，它必须有相同的哈希值。因此，引用和被引用的值有相同的哈希值。\texttt{Box}和被装箱的值有相同的哈希值。一个vector \texttt{vec}和包含它的所有元素的切片\texttt{\&vec[..]}有相同的哈希值。一个\texttt{String}和一个有相同字符的\texttt{\&str}有相同的哈希值。

结构和枚举默认没有实现\texttt{Hash}，但可以派生实现：
\begin{minted}{Rust}
    /// 大英博物馆藏品中的对象的ID
    #[derive(Clone, PartialEq, Eq, Hash)]
    enum MuseumNumber {
        ...
    }
\end{minted}
只要所有的字段都是可哈希的就可以正常工作。

如果你手动为一个类型实现了\texttt{PartialEq}，那你也应该手动实现\texttt{Hash}。例如，假设我们有一个类型表示无价的文物：
\begin{minted}{Rust}
    struct Artifact {
        id: MuseumNumber,
        name: String,
        cultures: Vec<Culture>,
        date: RoughTime,
        ...
    }
\end{minted}

并且有相同ID的两个\texttt{Artifact}被认为相等：
\begin{minted}{Rust}
    impl PartialEq for Artifact {
        fn eq(&self, other: &Artifact) -> bool {
            self.id == other.id
        }
    }

    impl Eq for Artifact {}
\end{minted}

因为我们比较两个文物时只根据ID进行比较，因此我们必须用相同的方式哈希它们：
\begin{minted}{Rust}
    use std::hash::{Hash, Hasher};

    impl Hash for Artifact {
        fn hash<H: Hasher>(&self, hasher: &mut H) {
            // 把哈希操作委托给MuseumNumber
            self.id.hash(hasher);
        }
    }
\end{minted}
（否则，\texttt{HashSet<Artifact>}将不能合适地工作；和所有哈希表一样，它要求如果\texttt{a == b}那么\texttt{hash(a) == hash(b)}。）

这样我们就可以创建一个\texttt{Artifact}的\texttt{HashSet}：
\begin{minted}{Rust}
    let mut collection = HashSet::<Artifact>::new();
\end{minted}

如上面的代码所示，即使你手动实现了\texttt{Hash}，你也不需要知道有关哈希算法的信息。\texttt{.hash()}接受一个\texttt{Hasher}的引用，后者代表哈希算法。你只需要把所有和\texttt{==}运算符相关的数据喂给\texttt{Hasher}。\texttt{Hasher}会从你给的内容计算出一个哈希值。

\section{使用一个自定义的哈希算法}

\texttt{hash}算法是泛型的，因此上面的\texttt{Hash}实现可以把数据喂给任何实现了\texttt{Hasher}的类型。这是Rust支持可插拔哈希算法的方式。

第三个trait，\texttt{std::hash::BuildHasher}，用于表示一个哈希算法的初始状态。每个\texttt{Hasher}只能使用一次，类似于一个迭代器：你只能使用它一次，然后就丢弃掉它。\texttt{BuildHasher}可以重用。

每一个\texttt{HashMap}都包含一个\texttt{BuildHasher}，每当需要计算一个哈希值都会使用它。\\
\texttt{BuildHasher}值包含哈希算法每次运行时需要的密钥、初始状态或其他参数。

计算一个哈希值的完整流程看起来像这样：
\begin{minted}{Rust}
    use std::hash::{Hash, Hasher, BuildHasher};

    fn compute_hash<B, T>(builder: &B, value: &T) -> u64
        where B: BuildHasher, T: Hash
    {
        let mut hasher = builder.build_hasher();  // 1. 开始算法
        value.hash(&mut hasher);                  // 2. 喂数据
        hasher.finish()                           // 3. 结束，产生一个u64
    }
\end{minted}

\texttt{HashMap}每次需要计算哈希值时都会调用这三个方法。所有的方法都是内联的，因此它的速度很快。

Rust的默认哈希算法是知名的SipHash-1-3算法。SipHash很快，并且擅长最小化哈希冲突。事实上，它是一种密码学安全算法：没有已知的有效方法来产生SipHash-1-3冲突。只要哈希表使用不同、不可预知的键，Rust可以抵御一种称为HashDos的拒绝服务攻击，这种攻击中攻击者故意利用哈希冲突来触发服务器性能最差的情况。

但你自己的应用可能不需要这样。如果你正在存储很多很小的键，例如整数或很短的字符串，那么你可以牺牲HashDos安全性来实现更快的哈希函数。\texttt{fnv} crate实现了这样一个算法，Fowler-Noll-Vo(FNV)哈希。在\emph{Cargo.toml}中加上一行来尝试它：
\begin{minted}{toml}
    [dependencies]
    fnv = "1.0"
\end{minted}

然后从\texttt{fnv}中导入map和set类型：
\begin{minted}{Rust}
    use fnv::{FnvHashMap, FnvHashSet};
\end{minted}

你可以用这两种类型作为\texttt{HashMap}和\texttt{HashSet}的替代。看一眼\texttt{fnv}的源码就知道它们是如何定义的：
\begin{minted}{Rust}
    /// 一个使用默认FNV hasher的 `HashMap`
    pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;

    /// 一个使用默认FNV hasher的 `HashSet`
    pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;
\end{minted}

标准的\texttt{HashMap}和\texttt{HashSet}接受一个可选的额外类型参数来指定哈希算法。\texttt{FnvHashMap}和\\
\texttt{FnvHashSet}是\texttt{HashMap}和\texttt{HashSet}的泛型类型别名，它将最后一个参数指定为FNV hasher。

\section{标准集合之外}

在Rust中创建一个新的自定义集合类型和在其他语言中差不多。通过组合语言提供的各个部分来排列数据：结构体和枚举、标准集合、\texttt{Option}、\texttt{Box}等等。例如，\nameref{GenEnum}中定义了\texttt{BinaryTree<T>}类型。

如果你习惯在C++中使用原始指针、手动内存管理、placement \texttt{new}、和手动析构调用来实现数据结构以获得最佳的性能，那么毫无疑问你会遇到安全Rust中的很多限制。所有这些工具都是天然不安全的。它们在Rust中也是可行的，但只能用于unsafe代码。\hyperref[ch22]{第22章}展示了为什么，并且还包含一个使用unsafe代码实现safe的自定义集合的示例。

到目前为止，我们都沉浸在标准集合及其安全、高效的API的温暖光芒中。和Rust标准库中很多其他部分一样，它们设计的目的之一是确保\texttt{unsafe}代码的需求尽可能减少。
